﻿#define _CRT_SECURE_NO_WARNINGS 1

//class Solution {
//public:
//    int longestSubsequence(vector<int>& arr, int difference) {
//        int n = arr.size();
//        int maxlen = 1;
//        unordered_map<int, int> dp{ {arr[0], 1} };
//        for (int i = 1; i < n; i++)
//        {
//            dp[arr[i]] = dp[arr[i] - difference] + 1;
//            maxlen = max(maxlen, dp[arr[i]]);
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int longestSubsequence(vector<int>& arr, int difference) {
//        int n = arr.size();
//        int maxlen = 1;
//        vector<int> dp(n, 1);
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (arr[i] - arr[j] == difference)
//                {
//                    dp[i] = dp[j] + 1;
//                    break;
//                }
//            }
//            maxlen = max(maxlen, dp[i]);
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int lenLongestFibSubseq(vector<int>& arr) {
//        int n = arr.size();
//        vector<vector<int>> dp(n, vector<int>(n));
//        unordered_map<int, int> hash;
//        int maxlen = 0;
//        for (int i = 0; i < n; i++) hash[arr[i]] = i;
//
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = i - 1; j > 0; j--)
//            {
//                int ret = arr[i] - arr[j];
//                if (ret < arr[j] && hash.find(ret) != hash.end())
//                {
//                    int k = hash[ret];
//                    dp[j][i] = max(dp[k][j] + 1, 3);
//                    maxlen = max(maxlen, dp[j][i]);
//                }
//            }
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int lenLongestFibSubseq(vector<int>& arr) {
//        int n = arr.size();
//        vector<vector<int>> dp(n, vector<int>(n));
//        int maxlen = 0;
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = i - 1; j > 0; j--)
//            {
//                int ret = arr[i] - arr[j];
//                vector<int>::iterator it = find(arr.begin(), arr.begin() + j, ret);
//                if (it != arr.begin() + j)
//                {
//                    int k = it - arr.begin();
//                    dp[j][i] = max(dp[k][j] + 1, 3);
//                    maxlen = max(dp[j][i], maxlen);
//                }
//            }
//        }
//        return maxlen;
//    }
//};